class List
{
    var arr;
    method List(length)
    {
        this.arr = array(length);
    }
    method List()
    {
        this.arr = array();
    }
    method Add(item)
    {
        array_push(this.arr, item);
    }
    method Get(index)
    {
        return this.arr[index];
    }
    method Set(index, value)
    {
        this.arr[index] = value;
    }
    method Length()
    {
        return array_size(this.arr);
    }
    method Print()
    {
        var i;
        var l = this.Length();
        print("[");
        for (i = 0; i < l; i = i + 1)
        {
            print(this.arr[i]);
            if (i != l - 1)
            {
                print(", ");
            }
        }
        println("]");
    }
}

function min(a, b)
{
    if (a < b)
        return a;
    else
        return b;
}

class TKnapsackItem
{
    var Weight, Cost, InSolution;
    method TKnapsackItem(inWeight, inCost)
    {
        this.Weight = inWeight;
        this.Cost = inCost;
        this.InSolution = 0;
    }
}

class TKnapsack
{
    var fnID;
    var fnMaxCapacity;
    var fnTotalItems;
    var fnIterations;
    var fnProcessingItemsCount;
    var fnTotalProcessingItemsCost;
    var fnTotalProcessingItemsWeight;
    var fnTotalProcessingItemsCostForDP;
    var fnProcessingItemsMaxCost;
    var fnMaxAllowedRelativeError;
    var frItems;
    var frProcessingItems;
    var faProcessingItemsAsArray;
    var faProcessingItemsCosts;
    var faProcessingItemsWeights;
    var faProcessingItemsCostsToEnd;
    var faProcessingItemsCostsForDP;
    var FormattedOutput;

    method TKnapsack(iaData, iaDataLen)
    {
        if (iaDataLen < 3)
        {
            println("Chybny vstup - byly ocekavany minimalne tri parametry.");
            exit(1);
        }
        this.fnID = parse_int(iaData[0]);
        this.fnTotalItems = parse_int(iaData[1]);
        this.fnMaxCapacity = parse_int(iaData[2]);
        this.frItems = new List();
        this.frProcessingItems = new List();
        this.fnIterations = 1;
        this.fnMaxAllowedRelativeError = 0;
        this.fnProcessingItemsMaxCost = 0;
        var lnMinParamCount = 3 + 2 * this.fnTotalItems;
        if (iaDataLen < lnMinParamCount)
        {
            print("Chybny vstup - bylo ocekavano minimalne ");
            print(lnMinParamCount);
            println(" parametru.");
            exit(2);
        }
        var i;
        for (i = 0; i < this.fnTotalItems; i = i + 1)
        {
            var lnWeight = parse_int(iaData[3 + i * 2]);
            var lnCost = parse_int(iaData[3 + i * 2 + 1]);
            this.frItems.Add(new TKnapsackItem(lnWeight, lnCost));
        }
        var frItemsLen = this.frItems.Length();
        for (i = 0; i < frItemsLen; i = i + 1)
        {
            // jistota je jistota - nebudu si pamatovat věci, které jsou samy o sobě težší než je kapacita batohu...
            // ...nebo ty, které nemají žádnou cenu
            var lrItem = this.frItems.Get(i);
            if (lrItem.Weight <= this.fnMaxCapacity && lrItem.Cost > 0)
            {
                this.frProcessingItems.Add(lrItem);
                if (lrItem.Cost > this.fnProcessingItemsMaxCost)
                    this.fnProcessingItemsMaxCost = lrItem.Cost;
            }
        }
        this.fnProcessingItemsCount = this.frProcessingItems.Length();
        this.fnTotalProcessingItemsCost = this.GetTotalCost(this.frProcessingItems);
        this.fnTotalProcessingItemsCostForDP = this.fnTotalProcessingItemsCost;
        this.fnTotalProcessingItemsWeight = this.GetTotalWeight(this.frProcessingItems);
        this.ComputeCostsToEnd();
        this.SetItemCostsAndWeights();
        this.faProcessingItemsAsArray = array(this.fnProcessingItemsCount);
        for (i = 0; i < this.fnProcessingItemsCount; i = i + 1)
        {
            this.faProcessingItemsAsArray[i] = this.frProcessingItems.Get(i);
        }
    }
    
    method GetTotalCost(irList)
    {
        var lnResult = 0, i;
        for (i = 0; i < irList.Length(); i = i + 1)
        {
            lnResult = lnResult + irList.Get(i).Cost;
        }
        return lnResult;
    }
    
    method GetTotalWeight(irList)
    {
        var lnResult = 0, i;
        for (i = 0; i < irList.Length(); i = i + 1)
        {
            lnResult = lnResult + irList.Get(i).Weight;
        }
        return lnResult;
    }
    
    method SetItemCostsAndWeights()
    {
        this.faProcessingItemsCosts = array(this.fnProcessingItemsCount);
        this.faProcessingItemsCostsForDP = array(this.fnProcessingItemsCount);
        this.faProcessingItemsWeights = array(this.fnProcessingItemsCount);
        var i;
        for (i = 0; i < this.fnProcessingItemsCount; i = i + 1)
        {
            this.faProcessingItemsCosts[i] = this.frProcessingItems.Get(i).Cost;
            this.faProcessingItemsCostsForDP[i] = this.frProcessingItems.Get(i).Cost;
            this.faProcessingItemsWeights[i] = this.frProcessingItems.Get(i).Weight;
        }
    }
    
    /// Pro každý prvek frSortedItems spočítá celkovou cenu věcí za tímto prvkem (včetně jeho samého).
    /// Uloží se to do pole faCostsToEnd a používá se to pro ořezávání prohledávaného stavového prostoru.
    method ComputeCostsToEnd()
    {
        this.faProcessingItemsCostsToEnd = array(this.fnProcessingItemsCount);
        var i, j, lnTotalCostToEnd;
        for (i = 0; i < this.fnProcessingItemsCount; i = i + 1)
        {
            lnTotalCostToEnd = 0;
            for (j = i; j < this.fnProcessingItemsCount; j = j + 1)
            {
                lnTotalCostToEnd = lnTotalCostToEnd + this.frProcessingItems.Get(i).Cost;
            }
            this.faProcessingItemsCostsToEnd[i] = lnTotalCostToEnd;
        }
    }
    
    method SolveByDynamicProgramming()
    {
        var lrResult = new List();
        var lnTableNSize = this.fnProcessingItemsCount + 1;
        var lnTableCSize = this.fnTotalProcessingItemsCostForDP + 1;
        var lnInfinity = this.fnTotalProcessingItemsWeight + 1;
        
        // to je naše tabulka pro řešení
        // první index je N a to je počet věcí, druhý index je C a to je cena, hodnota buňky je váha        
        var laSolvingSpace = array(lnTableNSize), i;
        for (i = 0; i < lnTableNSize; i = i + 1)
        {
            laSolvingSpace[i] = array(lnTableCSize);
        }
        
        // inicializace
        // T[*, 0] = 0
        // T[0, >0 ] = Infinity
        var n, c;
        for (n = 0; n < lnTableNSize; n = n + 1)
        {
            laSolvingSpace[n][0] = 0;
        }
        for (c = 1; c < lnTableCSize; c = c + 1)
        {
            laSolvingSpace[0][c] = lnInfinity;
        }
        
        // a jdeme na to!
        // T[N, C] = Min(T[N - 1, C], T[N - 1, C - C(N)] + W(N)) pro všechna i > 0.
        var lnCostIndex, lnNIndex, lnNewCostIndex, lnWeightIfPresent;
        for (lnCostIndex = 1; lnCostIndex < lnTableCSize; lnCostIndex = lnCostIndex + 1)
        {
            for (lnNIndex = 1; lnNIndex < lnTableNSize; lnNIndex = lnNIndex + 1)
            {
                // teď se snažím najít celkovou váhu řešení A, které má cenu lnCostIndex a je tam lnNIndex prvků

                // to je váha, kterou mělo řešení s cenou lnCostIndex, kde nebyla věc s pořadovým číslem lnNIndex
                var lnWeightIfNotPresent = laSolvingSpace[lnNIndex - 1][lnCostIndex];
                
                // a teď chci zjistit váhu, kterou mělo řešení, ze kterého by přidáním věci s pořadovým číslem lnNIndex
                // vzniklo řešení A

                // zjistím, jakou cenu mělo řešení, ze kterého by přidáním věci s pořadovým číslem lnNIndex vzniklo
                // řešení A - pozor, takové řešení ale nemusí vůbec existovat - třeba v případě, kdy moje A
                // je pro cenu 5 a 2 prvky a druhý prvek má cenu 10 - pak by původní cena byla -5

                // proč se do faItemCosts přistupuje indexem lnNIndex - 1? protože lnNIndex je N-index v tabulce
                // dynamického programování a má význam "počet prvků řešení", takže když chci cenu prvku N = lnIndex = 2,
                // tak musím odečíst 1, protože faItemCosts je indexované standardně od 0
                lnNewCostIndex = lnCostIndex - this.faProcessingItemsCostsForDP[lnNIndex - 1];
                if (lnNewCostIndex < 0)
                    lnWeightIfPresent = lnInfinity;
                else
                    lnWeightIfPresent = laSolvingSpace[lnNIndex - 1][lnNewCostIndex] + this.faProcessingItemsWeights[lnNIndex - 1];
                laSolvingSpace[lnNIndex][lnCostIndex] = min(lnWeightIfNotPresent, lnWeightIfPresent);
            }
        }
        
        // tak teď to máme napočítané, tak jdem zjistit, co to je vlastně za prvky

        // fáze 1 - zjisti cenu optimálního řešení
        var lnMaxCost = 0;
        for (lnCostIndex = lnTableCSize - 1; lnCostIndex >= 0; lnCostIndex = lnCostIndex - 1)
        {
            if (laSolvingSpace[lnTableNSize - 1][lnCostIndex] <= this.fnMaxCapacity)
            {
                lnMaxCost = lnCostIndex;
                lnCostIndex = -1;
            }
        }
        
        // fáze 2 - projdi tabulku a vytahej ty prvky
        var lnN = lnTableNSize - 1;
        var lnCost = lnMaxCost;
        
        // mám zaručeno, že vždy skončím na nulové ceně
        while (lnCost > 0)
        {
            if (laSolvingSpace[lnN][lnCost] == laSolvingSpace[lnN - 1][lnCost])
            {
                // věc s pořadovým číslem lnN v řešení není - posunu se doleva o 1
                lnN = lnN - 1;
            }
            else
            {
                // věc s pořadovým číslem lnN v řešení je - posunu se doleva o 1 a dolů o cenu prvku lnN
                lrResult.Add(this.frProcessingItems.Get(lnN - 1));
                lnCost = lnCost - this.faProcessingItemsCostsForDP[lnN - 1];
                lnN = lnN - 1;
            }
        }
        return lrResult;
    }
    
    method Solve()
    {
        var lnTotalCost = 0;
        var lnTotalWeight = 0;

        var lrResult = this.SolveByDynamicProgramming();

        lnTotalCost = this.GetTotalCost(lrResult);
        lnTotalWeight = this.GetTotalWeight(lrResult);

        print(this.fnID);
        print(" ");
        print(this.fnTotalItems);
        print(" ");
        print(lnTotalCost);
        print(" ");

        var items_len = this.frItems.Length();
        var result_len = lrResult.Length();
        var i;
        
        for (i = 0; i < result_len; i = i + 1)
        {
            lrResult.Get(i).InSolution = 1;
        }
            
        for (i = 0; i < items_len; i = i + 1)
        {
            if (this.frItems.Get(i).InSolution == 1)
                print(" 1");
            else
                print(" 0");
        }
        
        println("");
    }
}

function main(argc, argv)
{
    var lrKnapsack;
    if (argc == 2)
    {
        var laLines = read_lines(argv[1]);
        var len = array_size(laLines);
        var i;

        for (i = 0; i < len; i = i + 1)
        {

            var laArgs = string_split(laLines[i], " 	");
            lrKnapsack = new TKnapsack(laArgs, array_size(laArgs));
            lrKnapsack.Solve();
        }
    }
    else
    {
        lrKnapsack = new TKnapsack(argv, argc);
        lrKnapsack.Solve();
    }
    return 0;
}
